#include "seq-list.cpp"

/***
 * 快速排序
 * 基本思路: balabala...
 * 时间复杂度: 平均 O(nlogn) 最优O(nlogn) 最坏O(n^2)
 * 空间复杂度: O(nlogn)
 * 稳定性: 不稳定
 * */
int getIndex(SqList &L, int low, int high)
{
    int temp = L.data[low];
    while (low < high)
    {
        while (low < high && L.data[high] >= temp)
            high--;
        L.data[low] = L.data[high];
        while (low < high && L.data[low] <= temp)
            low++;
        L.data[high] = L.data[low];
    }
    L.data[low] = temp;

    return low;
}

void quickSort(SqList &L, int low, int high)
{
    if (low < high)
    {
        int index = getIndex(L, low, high);
        quickSort(L, low, index - 1);
        quickSort(L, index + 1, high);
    }
}

void sort(SqList &L)
{
    quickSort(L, 0, L.length-1);
}

int main(int argc, char const *argv[])
{
    SqList L;
    int data[6] = {6, 5, 3, 2, 7, 1};
    L.data = data;
    L.length = 6;
    printList(L);
    sort(L);
    printList(L);
    return 0;
}
